/*
A reasonable DisjointSet class is included:
      Constructor (2 pts)
      Find operation (5 pts)
      Union operation (5 pts)
      Path Compression implemented for even better run time (3 pts)
*/


public class DisjointSet {

	int[] ds;
	
	// Constructor
	DisjointSet (int setSize){
		ds = new int[setSize];
		
	}
	
    public void addMarker(int parent, int element){
    	ds[parent] = element;
    }
    
    public int getMarker (int element){
    	return ds[element];
    }

	public void Union(int parent, int element){
	   	ds[element] = Find(parent);
	}
	
	public int Find(int num){
		// follows the index's to each other index's and stops when the index
		// and the element are the same.
		// The count variable makes sure we don't get stuck
		// in a cycle
		
		int count = ds.length;
		while (ds[num] != num && count >= 0){
			num = ds[num];
			count--;
		}
		if (count == 0)
			return -1;
		else
		return num;
	}
	
	public String arrayToString(int startingPoint){
		
		if (startingPoint + 1 < ds.length){
			
			return this.toString(startingPoint) + " " + this.arrayToString(startingPoint + 1);
		}
		else
			return this.toString(startingPoint);
	}
	
	public String toString (int element){
		return String.valueOf(ds[element]);
	}
}
